# !/usr/usuari/des python
#  -*- coding: utf-8 -*-
"""
@Author        : itgnay
@Time          : 2022/12/25 19:24
@FileName      : 克鲁斯卡尔算法.py
@LastEditors   : None
@Editors       : PyCharm
"""
N = 6
cost_dict = {"0-1": 7, "1-3": 3, "0-3": 8, "1-2": 6, "3-2": 4, "3-4": 3, "2-4": 2, "2-5": 5, "4-5": 2}
cost = [[key, cost_dict[key]] for key in cost_dict]
point_list = ['S', 'A', 'B', 'C', 'D', 'T']


# 将所有边按权值大小做升序排序
# 这里用快速排序
def quick_sort(cost, p, q):
    if p >= q:
        return
    lo = p
    hi = q
    value = cost[q][1]
    while 1:
        if lo == hi:
            cost[lo], cost[q] = cost[q], cost[lo]
            break
        if cost[lo][1] <= value:
            lo += 1
        elif cost[hi][1] >= value:
            hi -= 1
        else:
            cost[lo], cost[hi] = cost[hi], cost[lo]
    quick_sort(cost, p, lo - 1)
    quick_sort(cost, lo + 1, q)


quick_sort(cost, 0, len(cost) - 1)


def kruskal_MinTree(cost, N):
    MinTree = [['', 0]] * (N - 1)
    assists = list(range(N))
    num = 0
    for i in range(len(cost)):
        p1, p2 = [int(p) for p in cost[i][0].split('-')]
        if assists[p1] == assists[p2]:
            continue
        else:
            MinTree[num] = cost[i]
            elem = assists[p2]
            for k in range(len(assists)):
                if assists[k] == elem:
                    assists[k] = assists[p1]
            num += 1
            if num > N - 2:
                return MinTree


mt = kruskal_MinTree(cost, N)
print("最小生成树:")
weight = 0
for s, w in mt:
    print('-'.join([point_list[i] for i in [int(p) for p in s.split('-')]]), 'weight', w)
    weight += w
print("总权值:", weight)
